Mathematical Foundations and Basic Concepts of Cryptography

John

Basic Cryptographic Definitions

Core Security Goals

  • Confidentiality: information is accessible only to authorized parties
  • Integrity: information hasn’t been altered by unauthorized parties
  • Authenticity: information originates from claimed source
  • Non-repudiation: sender cannot deny sending the message

Threat Models:

  • Passive adversary: Only observes communications (eavesdropper)
  • Active adversary: Can modify, insert, or delete messages
  • Adaptive adversary: Can change strategy based on observations

Key Concepts:

  • Plaintext/Ciphertext: Original message vs. encrypted message
  • Encryption/Decryption: Process of hiding/revealing information
  • Keys: Secret information used in cryptographic operations
  • Cryptanalysis: The art of breaking cryptographic systems

Real world example:

  • Scenario: Alice wants to transfer $1000 to Bob through online banking.
  • Confidentiality: The transaction details are encrypted so eavesdroppers can’t see the amount or recipient.
  • Integrity: The bank can detect if someone tries to change $1000 to $10000 during transmission.
  • Authenticity: The bank verifies that Alice actually initiated the transaction.
  • Non-repudiation: Alice cannot later claim she never authorized the transfer.

 

Historically Classic Ciphers

Substitution Ciphers:

  • Caesar Cipher: Each letter shifted by fixed amount
  • Monoalphabetic Substitution: Each letter mapped to different letter
  • Polyalphabetic Ciphers: Multiple substitution alphabets (Vigenère)

Transposition Ciphers:

  • Columnar Transposition: Rearrange letters according to key
  • Rail Fence: Write message in zigzag pattern

Cryptanalysis Techniques:

  • Frequency Analysis: Exploiting letter frequency patterns
    • Exploits the fact that some letters appear more frequently than others in natural language. ‘E’ is most common in English (~12.7%).
  • Pattern Recognition: Common words like “THE”, “AND”, “OF” create recognizable patterns even when encrypted.
  • Index of Coincidence: Measuring randomness. Measures how similar a text is to English. Random text has IC ≈ 0.038, English has IC ≈ 0.067.
  • Kasiski Examination: Finding repeated patterns. For Vigenère ciphers, finds repeated sequences to determine key length.

 

Perfectly Secret Encryption and Shannon’s Theorem

Perfect Secrecy (Information-Theoretic Security):

  • Ciphertext reveals no information about plaintext
  • Formally: P(M=m|C=c) = P(M=m) for all m, c
  • Security holds even against computationally unbounded adversaries

Shannon’s Theorem:

  • Necessary condition: |K| ≥ |M| (key space ≥ message space)
  • Sufficient condition: One-Time Pad achieves perfect secrecy
  • Trade-off: Perfect security requires very long keys

One-Time Pad Properties:

  • Key is random, as long as message, used only once
  • Encryption: C = M ⊕ K (XOR operation)
  • Decryption: M = C ⊕ K
  • Limitations: Key distribution and key reuse vulnerabilities

 

Number Theory and Generating Primes

Fundamental Number Theory:

  • Modular Arithmetic: Computing with remainders (a ≡ b (mod n))
  • Greatest Common Divisor (GCD): Euclidean Algorithm and Extended GCD
  • Euler’s Totient Function: φ(n) = count of integers ≤ n that are coprime to n
  • Chinese Remainder Theorem: Solving systems of congruences

Prime Numbers and Testing:

  • Primality Testing: Deterministic vs. Probabilistic methods
  • Fermat’s Little Theorem: If p is prime, then a^(p-1) ≡ 1 (mod p)
  • Miller-Rabin Test: Efficient probabilistic primality test
  • Prime Generation: Creating large primes for cryptographic use

Applications in Cryptography:

  • RSA Key Generation: Finding large primes p and q
  • Discrete Logarithm Problem: Foundation for many crypto systems
  • Modular Exponentiation: Efficient algorithms for computing a^b mod n

 

 

Fundamental Number Theory Topics

1. Modular Arithmetic

Core Concepts:

Definition: Two integers a and b are congruent modulo n if n divides (a – b)

  • Notation: a ≡ b (mod n)
  • Example: 17 ≡ 5 (mod 12) because 12 divides (17 – 5 = 12)

Properties:

  • Reflexive: a ≡ a (mod n)
  • Symmetric: If a ≡ b (mod n), then b ≡ a (mod n)
  • Transitive: If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
  • Addition: If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n)
  • Multiplication: If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n)

Applications in Cryptography:

  • All RSA computations are done modulo n = pq
  • Discrete logarithm problems work in multiplicative groups mod p
  • Hash functions often use modular arithmetic for efficiency

Example:

Computing 7³ mod 13:
7³ = 343
343 = 26 × 13 + 5
Therefore: 7³ ≡ 5 (mod 13)

2. Greatest Common Divisor (GCD) and Extended Euclidean Algorithm

Euclidean Algorithm:

Purpose: Efficiently compute gcd(a,b)

Algorithm:
while b ≠ 0:
    r = a mod b
    a = b
    b = r
return a

Example: gcd(48, 18)

  • 48 = 2×18 + 12
  • 18 = 1×12 + 6
  • 12 = 2×6 + 0
  • Therefore: gcd(48, 18) = 6

Extended Euclidean Algorithm:

Purpose: Find integers x, y such that ax + by = gcd(a,b)

Cryptographic Importance:

  • Modular Inverses: To find a⁻¹ mod n, solve ax ≡ 1 (mod n)
  • RSA Key Generation: Computing d such that ed ≡ 1 (mod φ(n))
  • Chinese Remainder Theorem: Solving systems of congruences

Example: Find 15⁻¹ mod 26

26 = 1×15 + 11    →    11 = 26 - 1×15
15 = 1×11 + 4     →    4 = 15 - 1×11 = 15 - 1×(26 - 1×15) = 2×15 - 1×26
11 = 2×4 + 3      →    3 = 11 - 2×4 = (26 - 1×15) - 2×(2×15 - 1×26) = 3×26 - 5×15
4 = 1×3 + 1       →    1 = 4 - 1×3 = (2×15 - 1×26) - 1×(3×26 - 5×15) = 7×15 - 4×26

Therefore: 15⁻¹ ≡ 7 (mod 26)
Verification: 15 × 7 = 105 ≡ 1 (mod 26) ✓

3. Euler’s Totient Function φ(n)

Definition:

φ(n) = number of positive integers ≤ n that are relatively prime to n

Key Formulas:

  • For prime p: φ(p) = p – 1
  • For prime power: φ(p^k) = p^k – p^(k-1) = p^(k-1)(p – 1)
  • For coprime integers: φ(mn) = φ(m)φ(n) if gcd(m,n) = 1
  • For RSA modulus: φ(pq) = (p-1)(q-1) where p, q are distinct primes

Examples:

  • φ(12) = φ(4 × 3) = φ(2²) × φ(3) = (2¹)(2-1) × (3-1) = 2 × 2 = 4
    • Numbers coprime to 12: {1, 5, 7, 11}
  • φ(15) = φ(3 × 5) = φ(3) × φ(5) = 2 × 4 = 8
    • Numbers coprime to 15: {1, 2, 4, 7, 8, 11, 13, 14}

Cryptographic Applications:

  • Euler’s Theorem: If gcd(a,n) = 1, then a^φ(n) ≡ 1 (mod n)
  • RSA Decryption: Uses the fact that m^φ(n) ≡ 1 (mod n)
  • Key Generation: φ(n) determines valid exponents in RSA

4. Chinese Remainder Theorem (CRT)

Statement:

If n₁, n₂, …, nₖ are pairwise coprime, then the system:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)

has a unique solution modulo N = n₁n₂…nₖ

Construction Algorithm:

  1. Compute N = n₁n₂…nₖ
  2. For each i, compute Nᵢ = N/nᵢ
  3. Find Mᵢ such that NᵢMᵢ ≡ 1 (mod nᵢ)
  4. Solution: x ≡ Σ(aᵢNᵢMᵢ) (mod N)

Example:

Solve:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Solution:

  • N = 3 × 5 × 7 = 105
  • N₁ = 35, M₁ = 2 (since 35×2 ≡ 1 (mod 3))
  • N₂ = 21, M₂ = 1 (since 21×1 ≡ 1 (mod 5))
  • N₃ = 15, M₃ = 1 (since 15×1 ≡ 1 (mod 7))
  • x ≡ 2×35×2 + 3×21×1 + 2×15×1 ≡ 140 + 63 + 30 ≡ 23 (mod 105)

Cryptographic Applications:

  • RSA Speed-up: Decrypt using CRT with p and q separately, then combine
  • Secret Sharing: Distribute secrets across multiple moduli
  • Multiparty Computation: Enable parallel computations

5. Fermat’s Little Theorem and Primality Testing

Fermat’s Little Theorem:

If p is prime and gcd(a,p) = 1, then:

a^(p-1) ≡ 1 (mod p)

Fermat Primality Test:

Input: n (candidate prime), k (iterations)
for i = 1 to k:
    choose random a in [2, n-2]
    if a^(n-1) ≢ 1 (mod n):
        return "composite"
return "probably prime"

Problem: Carmichael numbers (composite numbers that pass Fermat test for all bases coprime to them)

  • Example: 561 = 3 × 11 × 17 is composite but a^560 ≡ 1 (mod 561) for all gcd(a,561) = 1

Miller-Rabin Test (Improved):

Key Insight: If n is odd prime and n-1 = 2^r × d (d odd), then for any a:

  • Either a^d ≡ 1 (mod n)
  • Or a^(2^j × d) ≡ -1 (mod n) for some 0 ≤ j ≤ r-1
Miller-Rabin Algorithm:
Input: n, k
Write n-1 = 2^r × d with d odd
for i = 1 to k:
    choose random a in [2, n-2]
    x = a^d mod n
    if x = 1 or x = n-1:
        continue
    for j = 1 to r-1:
        x = x² mod n
        if x = n-1:
            continue to next iteration
    return "composite"
return "probably prime"

Advantages:

  • No known composite numbers that consistently pass Miller-Rabin
  • Error probability ≤ (1/4)^k for k iterations
  • Practical and efficient for large numbers

6. Modular Exponentiation

Fast Exponentiation Algorithm:

Computing a^b mod n efficiently using binary representation of b.

Algorithm:
result = 1
base = a mod n
while b > 0:
    if b is odd:
        result = (result × base) mod n
    b = b >> 1  // right shift (divide by 2)
    base = (base × base) mod n
return result

Example: 3^13 mod 7

  • 13 = 1101₂ (binary)
  • 3¹ mod 7 = 3
  • 3⁴ mod 7 = (3²)² mod 7 = 9² mod 7 = 4
  • 3⁸ mod 7 = (3⁴)² mod 7 = 4² mod 7 = 2
  • 3¹³ mod 7 = 3⁸ × 3⁴ × 3¹ mod 7 = 2 × 4 × 3 mod 7 = 3

Time Complexity: O(log b) multiplications instead of O(b)

Applications in Cryptography

RSA Key Generation Process:

  1. Choose primes p, q: Use Miller-Rabin to test candidates
  2. Compute n = pq: The RSA modulus
  3. Compute φ(n) = (p-1)(q-1): Using totient function
  4. Choose e: Such that gcd(e, φ(n)) = 1, typically e = 65537
  5. Compute d: Using extended Euclidean algorithm: ed ≡ 1 (mod φ(n))

Security Foundations:

  • Factoring Problem: Given n = pq, find p and q (hard for large n)
  • RSA Problem: Given (n, e, c), find m such that m^e ≡ c (mod n)
  • Discrete Log Problem: Given g, y, p, find x such that g^x ≡ y (mod p)

These number-theoretic foundations are essential because they provide both the mathematical structure needed for cryptographic algorithms and the computational hardness assumptions that guarantee security.